#!/usr/bin/env python2
# -*- coding: utf-8 -*-

import re
import copy
import lab2
import itertools
import random

r1 = "^.*1.*1.*1.*$" # не меньше трёх единиц
r2 = "^(.....|....|...|..|.|)$" # не более 5-ти символов
r3 = "(^$|^0$)" # явл. пустой строкой или нулём
r4 = "^((1*01*1*01*)*|0*10*10*)$" # сод. четное число нулей, или в точности две единицы

#r5_ = '^0*|0*10*|1*$'
r5_ = '^(0*10)*(0*|1*)$'

def dfa_to_regexp(transitions, final):
    """
    Takes DFA's transitions table (transitions), starting state (start) and
    a set of final states (final) and returns a regular expression matching
    that DFA.
    """
    n = len(transitions)
    if n == 0:
        return None

    # translates transitions table into some sort of adjacency matrix with regexps
    gnfa = [[None] * (n + 1) for i in range(n + 1)]
    gnfa[n][0] = ''
    for i in range(n):
        for j in range(n):
            r = '|'.join(c for c in transitions[i]
                         if transitions[i][c] == j)
            if r:
                gnfa[i][j] = r

    for q in final:
        gnfa[q][n] = ''

    return reduce_gnfa(gnfa)

def reduce_gnfa(gnfa):
    for n in range(len(gnfa) - 2, -1, -1):
        remove_node(gnfa, n)
    return '^(%s)$' % (gnfa[-1][-1],)

def remove_node(gnfa, n):
#   print "removing", n
    states = range(n) + [len(gnfa) - 1]
    for (i, j) in itertools.product(states, repeat=2):
        if gnfa[i][n] != None != gnfa[n][j]: # gnfa[i][n] != None and gnfa[n][j] != None
            replace_path(gnfa, i, n, j)
#   for i in states:
#       for j in states:
#           print "'", gnfa[i][j], "'", '\t',
#       print
#   print

def replace_path(gnfa, i, n, j):
    nn_re = ''
    ij_re = ''
    if gnfa[n][n]:
        nn_re = '(' + gnfa[n][n] + ')*'
    if gnfa[i][j]:
        ij_re = '|(' + gnfa[i][j] + ')'
    gnfa[i][j] = "(%s)%s(%s)%s" % (gnfa[i][n], nn_re, gnfa[n][j], ij_re)

transitions1 = [{} for i in range(3)]
transitions1[0]['a'] = 1
transitions1[0]['b'] = 0
transitions1[1]['a'] = transitions1[1]['b'] = 2
transitions1[2]['a'] = 1
transitions1[2]['b'] = 0

def test_conversion(transitions, final, n):
    m = lab2.make_dfa(transitions, final)
    r = dfa_to_regexp(transitions, final)

    alphabet = transitions[0].keys()
    w = ''.join(random.choice(alphabet) for i in range(n))
    print w, '\t', m(w), bool(re.search(r, w))

    return m(w) == bool(re.search(r, w))

if __name__ == "__main__":
    transitions1_regexp = dfa_to_regexp(transitions1, [1])
    print transitions1_regexp
    for i in range(20):
        test_conversion(transitions1, [1], i)
